package leetcode_题库;

import java.util.Stack;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/25 9:36 星期四
 */
public class _232_用栈实现队列 {

    /**
     * 双栈实现队列
     * 我们令data为存储数据的唯一栈，令temp为临时栈
     * 当data为空，则整体为空，直接往data插入一条即可
     * 若data不为空，先将数据转移给temp，当data插入新数据后，再转移过来，其实复杂度很高（几乎达到了题目要求的100次），但是耗时很低。。。。
     *
     * > 2022/08/25 09:56:41
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:39.1 MB,击败了75.78% 的Java用户
     */

    private Stack<Integer> data;
    private Stack<Integer> temp;

    public _232_用栈实现队列() {
        data = new Stack<>();
        temp = new Stack<>();
    }

    public void push(int x) {
        if (data.isEmpty()){
            data.push(x);
            return;
        }
        while (!data.isEmpty()){
            temp.push(data.pop());
        }
        data.push(x);
        while (!temp.isEmpty()){
            data.push(temp.pop());
        }
    }

    public int pop() {
        return data.pop();
    }

    public int peek() {
        return data.peek();
    }

    public boolean empty() {
        return data.isEmpty();
    }

    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue obj = new MyQueue();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.peek();
     * boolean param_4 = obj.empty();
     */
}

class _232_用栈实现队列_方法2 {
    /**
     * 来自评论的另一个解释，感觉性能较好
     * input只负责入栈，所以push(int x)非常好写
     * output只负责出栈，当output为空，把input所有内容都入栈给output，再出栈，peek同理，但peek和pop的复杂度较高，不如我的写法
     * 判断为空时，两个同时为空才说明总栈为空
     *
     * > 2022/08/25 10:09:06
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:39 MB,击败了94.15% 的Java用户
     */
    private Stack<Integer> input;
    private Stack<Integer> output;

    public _232_用栈实现队列_方法2() {
        input = new Stack<>();
        output = new Stack<>();
    }

    public void push(int x) {
        input.push(x);
    }

    public int pop() {
        if (output.isEmpty()){
            while (!input.isEmpty()){
                output.push(input.pop());
            }
        }
        return output.pop();
    }

    public int peek() {
        if (output.isEmpty()){
            while (!input.isEmpty()){
                output.push(input.pop());
            }
        }
        return output.peek();
    }

    public boolean empty() {
        return output.isEmpty() && input.isEmpty();
    }

    /**
     * Your MyQueue object will be instantiated and called as such:
     * MyQueue obj = new MyQueue();
     * obj.push(x);
     * int param_2 = obj.pop();
     * int param_3 = obj.peek();
     * boolean param_4 = obj.empty();
     */
}
